package io.adrainty.algorithm.mars;

/**
 * @author adrainty
 * @version v1.0.0
 * @since 2024/11/29 下午4:56
 */
public class Solution019 {

    private Solution019() {}

    /**
     * 小U拥有一个由0和1组成的字符串，她可以进行最多k次操作，每次操作可以交换相邻的两个字符。
     * 目标是通过这些操作，使得最终得到的字符串字典序最小。
     * @param n 字符串的长度
     * @param k 能操作的次数
     * @param s 字符串
     * @return 能够得到的字典序最小的字符串
     */
    public static String solution(int n, int k, String s) {
        // write code here
        if (k == 0 || s.length() <= 1) return s;
        char[] chars = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            if (k <= 0) break;
            if (i + 1 >= s.length()) break;
            if (chars[i] == '1') {
                // 看在最近k个字符里面能不能找到0
                int temp = 1;
                while (temp <= k && i + temp < s.length()) {
                    if (chars[i + temp] == '0') {
                        swap(chars, i, i + temp);
                        k -= temp;
                        break;
                    }
                    temp++;
                }
            }
        }
        return new String(chars);
    }

    /**
     * 交换两个字符, 实际上是j移动到i 其他的字符往后一位
     * @param chars 原始数组
     * @param i 开始交换的位置
     * @param j 结束交换的位置
     */
    private static void swap(char[] chars, int i, int j) {
        char temp = chars[j];
        for (int k = j; k > i; k--) {
            chars[k] = chars[k - 1];
        }
        chars[i] = temp;
    }

}
